class Solution {

    private int n;
    private int m;
    private boolean[][] visit;
    private Queue<Pair<Integer,Integer>> queue;
    private char[][] board;

    public void solve(char[][] board) {
        this.board = board;
        n = board.length;
        m = board[0].length;
        queue = new LinkedList<>();
        visit = new boolean[n][m];
        //遍历四条边
        for(int i=0; i<n; i++){
            if(board[i][0]=='O'&&!visit[i][0]) bfs(i,0,false);
        }
        for(int i=0; i<n; i++){
            if(board[i][m-1]=='O'&&!visit[i][m-1]) bfs(i,m-1,false);
        }
        for(int i=0; i<m; i++){
            if(board[0][i]=='O'&&!visit[0][i]) bfs(0,i,false);
        }
        for(int i=0; i<m; i++){
            if(board[n-1][i]=='O'&&!visit[n-1][i]) bfs(n-1,i,false);
        }
        //替换被'X'包围的'O'
        for(int i=0; i<n; i++){
            for(int j=0; j<m; j++){
                if(board[i][j]=='O'&&!visit[i][j]) bfs(i,j,true);
            }
        }
    }

    //遍历相邻'O'区域
    private void bfs(int x, int y, boolean replace){
        int[] dx = {0, 0, -1, 1};
        int[] dy = {1, -1, 0 ,0};
        queue.offer(new Pair<Integer,Integer>(x,y));
        visit[x][y] = true;
        while(!queue.isEmpty()){
            int cx = queue.peek().getKey();
            int cy = queue.poll().getValue();
            if(replace) board[cx][cy]='X';
            for(int i=0; i<4; i++){
                int nx = cx + dx[i];
                int ny = cy + dy[i];
                if(nx<0||ny<0||nx>=n||ny>=m)continue;
                if(board[nx][ny]=='O'&&!visit[nx][ny]){
                    queue.offer(new Pair<Integer,Integer>(nx,ny));
                    visit[nx][ny]=true;
                }
            }
        }
    }
}
/**
    1、从边上的'O'开始，遍历跟他相邻的区域，标记为已访问
    2、遍历还未标记的'O'，并修改成'X'
 */